#include <stdio.h>
#include <stdlib.h>
#include "fatal.h"

typedef int ElementType;
typedef ElementType ItemType[2];

struct KdNode;
typedef struct KdNode *Position;
typedef struct KdNode *KdTree;

struct KdNode {
	ItemType Data;
	KdTree Left;
	KdTree Right;
};

/* START: fig12_43.txt */
static KdTree RecursiveInsert(ItemType Item, KdTree T, int Level) {
	if (T == NULL) {
		T = malloc(sizeof(struct KdNode));
		if (T == NULL)
			FatalError("Out of space!!!");
		T->Left = T->Right = NULL;
		T->Data[0] = Item[0];
		T->Data[1] = Item[1];
	} else if (Item[Level] < T->Data[Level])
		T->Left = RecursiveInsert(Item, T->Left, !Level);
	else
		T->Right = RecursiveInsert(Item, T->Right, !Level);
	return T;
}

KdTree Insert(ItemType Item, KdTree T) {
	return RecursiveInsert(Item, T, 0);
}
/* END */

/* START: fig12_44.txt */
/* Print items satisfying */
/* Low[ 0 ] <= Item[ 0 ] <= High[ 0 ] and */
/* Low[ 1 ] <= Item[ 1 ] <= High[ 1 ] */

static void RecPrintRange(ItemType Low, ItemType High, KdTree T, int Level) {
	if (T != NULL) {
		if (Low[0] <= T->Data[0] && T->Data[0] <= High[0]
				&& Low[1] <= T->Data[1] && T->Data[1] <= High[1])
			printf("(%d,%d)\n", T->Data[0], T->Data[1]);

		if (Low[Level] <= T->Data[Level])
			RecPrintRange(Low, High, T->Left, !Level);
		if (High[Level] >= T->Data[Level])
			RecPrintRange(Low, High, T->Right, !Level);
	}
}

void PrintRange(ItemType Low, ItemType High, KdTree T) {
	RecPrintRange(Low, High, T, 0);
}
/* END */

main() {
	KdTree T;
	ItemType It, L, H;
	int i;

	printf("Starting program\n");

	T = NULL;
	for (i = 300; i < 370; i++) {
		It[0] = i;
		It[1] = 2500 - i;
		T = Insert(It, T);
	}

	printf("Insertions complete\n");

	i = 1;
	L[0] = 70;
	L[1] = 2186;
	H[0] = 1200;
	H[1] = 2200;
	PrintRange(L, H, T);

	printf("Done...\n");
	return 0;
}

